home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part1 / 8170 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.8 KB
  1. Path: newshub.alcatel.no!STKT22
  2. From: Sven.Pran@alcatel.no (Sven Pran)
  3. Newsgroups: comp.lang.pascal.misc,comp.lang.c++,comp.lang.c,comp.lang.pascal.borland
  4. Subject: Re: Tough FACTORIAL math problem...
  5. Date: Thu, 15 Feb 96 11:50:11 GMT
  6. Organization: Alcatel Network Services, Norway
  7. Message-ID: <4fv74c$chq@gatekeeper.alcatel.no>
  8. References: <4fr8be$ass@news.iconn.net> <31224679.6193@born.com>
  9. NNTP-Posting-Host: stkt22.alcatel.no
  10. X-Newsreader: News Xpress Version 1.0 Beta #4
  11.  
  12. In article <31224679.6193@born.com>, John Cleland <clelaj@born.com> wrote:
  13. >The Crow wrote:
  14. >> 
  15. >> Here is what I am trying to do, I want to find the last NON-ZERO digit of a
  16. >> given factorial.  For instance,
  17. >> 
  18. >> 5! = 120
  19. >> 
  20. >> so the last non-zero digit is 2.  I want to be able to do this up to 1000.
  21. >> Problem is, no matter how huge of a data-type you use, there isn't any way 
  22. >> for the computer to handle 1000!, it is however possible to find the last 
  23. >> non-zero digit somehow.  One thing I have tried is as I went through 
  24. >> multiplying the series of numbers in the factorial (5 * 4 * 3 * 2) I would 
  25. >> remove all the trailing ZEROS, I got this to work up to 789, but it wont 
  26. >> work with 1000 and i am not really sure why.  If anyone has a clue how I 
  27. >> can do this let me know.
  28. >
  29. >Don't just strip the trailing zeros, remove all digits except the last 
  30. >non-zero digit (which is your output) and then multiply by the next number in 
  31. >your sequence. This keeps the numbers down to a managable level and gives the 
  32. >correct answer as no more significant digit can affect the value of the LSD.
  33. >
  34.  . . . .
  35.  
  36. No, it is obviously not sufficient to keep the last single non-zero digit, and 
  37. the problem appears to be a very interesting and intriguing one:
  38.  
  39. A new trailing zero is 'created' every time the next multiplier is divisible 
  40. by 5, and how can we then calculate the next 'rightmost significant' digit?
  41.  
  42. Example when a multiplier ends in 05:
  43.  
  44. If the 'previous' factorial ended in 02 then the new factorial will end in 1 
  45. while if it ended in 12 then the new factorial will end in 6 (after removal of 
  46. trailing zeroes).
  47.  
  48. Thus the SINGLE rightmost significant digit in the new factorial depends upon 
  49. the TWO rightmost significant digits both in the previous factorial and in the 
  50. multiplier.
  51.  
  52. This means that we must keep track of the last TWO digits to calculate the new 
  53. SINGLE rightmost significant digit whenever a zero is 'created'. For similar 
  54. reasons we must track THREE digits to calculate the new TWO rightmost 
  55. significant digits - and so on.
  56.  
  57. How many zeroes have been 'removed' when we reach 1000! ? The answer is 249, 
  58. which means that in order to maintain the precision needed we must track the 
  59. last 250 digits less the number of zeroes already 'removed' when N! reaches a 
  60. number with that many digits.
  61.  
  62. This is where I get stuck. Hey - number theory specialists: How do we proceed?
  63.  
  64. regards Sven
  65.